import java.util.Stack;

public class BSTIterator {

    TreeNode root;
    Stack<TreeNode> stack;
    public BSTIterator(TreeNode root) {
        this.root = root;
        stack = new Stack<>();
        stack.push(root);
        while (root.left != null) {
            stack.push(root.left);
            root = root.left;
        }
    }

    public int next() {
        TreeNode out = stack.pop();
        TreeNode temp = out;
        if (temp.right != null) {
            stack.push(temp.right);
            temp = temp.right;
            while (temp.left != null) {
                stack.push(temp.left);
                temp = temp.left;
            }
        }
        return out.val;
    }

    public boolean hasNext() {
        return stack.isEmpty();
    }
}
